//
// Created by yanhai on 2021/1/3.
//

// 希尔排序

#include <stdio.h>

#define ARRAY_DATA_LENGTH 16

void print(int *data, int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

// 如果一个记录基本上接近是有序的，那么直接插入排序效率是很高的，因为只需要少量的插入操作，就可以完成整个记录集的排序工作。
// 还有就是记录数比较少的时候，直接插入排序优势也比较明显。
//
// 希尔排序就是为直接插入排序创造这样的条件，让它每次排序都尽可能的少的元素或尽可能接近有序的元素参与排序
// 让直接插入排序的优势发挥出来。
// 第1步，将他们分成很多组，每组只有2个元素，让它们使用直接插入排序，每组都变成有序状态。 这满足了直接插入排序的 元素较少时效率高的特点
// 第2步，将分组减少，每组的元素变多了一点，但是它们相比于没有初始状态下，经过了第1步，有序的程度较高了一些。
// 第3步，再将分组减少，此时的每组的元素增多，但每组的有序程序都比之前更好了
// 经过n次之后，当分组是有1个的时候，此时的整个记录是基本有序的了，此时再次使用直接插入排序对整个记录排序，效率将非常的好，
// 因为这满足了，上面第一句话。
//
// 这里的基本有序：就是小的元素基本上在前面，大的元素基本上在后面，不大不小的元素基本在中间
// 因此，如何分组，是关键
// 将相距某个"增量"的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
// 注意：1。增量序列的最后一个增量值必须等于1才行（因为要完整的对整个集合排序）
//      2。由于元素是跳跃式的移动，因此希尔排序并不是一种稳定的排序算法。
void shell_sort(int *data, int length)
{
    int gap = 0;
    int i = 0, j = 0;
    int temp = 0;

    // 先让每组2个元素，length/2就是组数，也就是"增量"
    // 然后依次降低组数，直到增量为1，此时就剩1组了，也就是整个待排集合
    for (gap = length / 2; gap >= 1; gap /= 2) {
        // 对每组使用直接插入排序方法
        for (i = gap; i < length; i++) {
            temp = data[i];
            // 下面的代码，对比上一篇的直接插入排序，gap就是1
            // 这里是希尔排序的精华所在，它将较小的元素，不是一步一步往前挪动，而是跳跃式的向前移
            // 从而使得每次完成最外层的for循环一次，整个序列就朝着有序坚实的迈进一步。
            for (j = i - gap; j >= 0 && temp < data[j]; j = j - gap) {
                data[j + gap] = data[j];
            }
            data[j + gap] = temp;
        }
    }
}

int main()
{
    int data[ARRAY_DATA_LENGTH] = {71, 64, 24, 12, 9, 16, 53, 57, 23, 79, 87, 97, 45, 60, 61, 90};

    print(data, ARRAY_DATA_LENGTH);
    shell_sort(data, ARRAY_DATA_LENGTH);
    print(data, ARRAY_DATA_LENGTH);

    return 0;
}
